/**
 * 
 */
package tree.passed2;

/**
 * @author xyyi
 *
 */
public class SymmetricTree {

	/**
	Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

	For example, this binary tree is symmetric:

	1
	/ \
	2   2
	/ \ / \
	3  4 4  3

	But the following is not:

	1
	/ \
	2   2
	\   \
	3    3

	Note:
	Bonus points if you could solve it both recursively and iteratively.
	 */
	public boolean isSymmetric(TreeNode root) {
		if (root == null)
			return true;
		return isSymmetric(root.left, root.right);

	}

	private boolean isSymmetric(TreeNode n1, TreeNode n2) {
		if (n1 == null && n2 == null)
			return true;
		if (n1 == null || n2 == null)
			return false;

		return n1.val == n2.val && isSymmetric(n1.left, n2.right)
				&& isSymmetric(n1.right, n2.left);
	}
	
    private boolean isSysmetricHelper(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;
        return left != null && right != null && left.val == right.val && isSysmetricHelper(left.left, right.right) && isSysmetricHelper(left.right, right.left);
    }

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public SymmetricTree() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
